
"""
1143. 最长公共子序列
https://leetcode.cn/problems/longest-common-subsequence/

输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace" ，它的长度为 3 。
"""


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        size1 = len(text1)
        size2 = len(text2)

        # (size2+1) * (size1+1)的矩阵
        dp = [[0 for _ in range(size2+1)] for _ in range(size1+1)]
        for i in range(size1+1):  # 逐行 
            for j in range(size2+1):  # 逐列
                if i == 0 or j == 0:
                    # 表示有一個是空串的時候
                    dp[i][j] = 0
                else:
                    # 状态转移方程
                    if text1[i-1] == text2[j-1]:
                        dp[i][j] = 1 + dp[i-1][j-1]
                    else:
                        dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        print(dp)
        return dp[i][j]


def test():
    obj = Solution()
    res = obj.longestCommonSubsequence('abcde', "ace")
    print(res)


if __name__ == "__main__":
    test()